#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>
#include <stack>
#include <unordered_map>

using namespace std;


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/**
 * 自己的 96ms
 */
class Solution1 {
public:
    TreeNode* build(vector<int>& preorder,int ps,int pe ,vector<int>& inorder,int is,int ie){
        // cout << "ps: "<< ps << " pe: "<< pe << " is: "<< is << " ie: "<<ie <<endl;
        //边界处理
        if(ps>pe||is>ie){
            return nullptr;
        }
        auto it=find(inorder.begin(),inorder.end(),preorder[ps]);
        int index=it-inorder.begin();
        TreeNode *root=new TreeNode(preorder[ps]);
        root->left=build(preorder,ps+1,ps+index-is,inorder,is,index-1);
        root->right=build(preorder,ps+index-is+1,pe,inorder,index+1,ie);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }
};
/**
大佬写的 8ms
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0) return NULL;
        TreeNode* root = new TreeNode(preorder[0]);
        stack<TreeNode*> s;
        s.push(root);
        int inidx = 0,sz=preorder.size();
        for(int i=1; i<sz; i++){
            TreeNode* temp = s.top();
            if(temp->val!=inorder[inidx]){
                temp->left = new TreeNode(preorder[i]);
                s.push(temp->left);
            }else{
                while((!s.empty())&&s.top()->val==inorder[inidx]){
                    temp = s.top(); s.pop();
                    inidx++;
                }
                temp->right = new TreeNode(preorder[i]);
                s.push(temp->right);
            }
        }
        return root;
    }
};




void pretravel(TreeNode *head){
    if(head!=nullptr){
        cout << head->val<< " ";
        pretravel(head->left);
        pretravel(head->right);
    }
}
int main(){
    vector<int> preorder={3,9,8,5,4,10,20,15,7};
    vector<int> inorder={4,5,8,10,9,3,15,20,7};
    // vector<int> preorder={3,9,20,15,7};
    // vector<int> inorder={9,3,15,20,7};
    Solution s;
    TreeNode *p=s.buildTree(preorder,inorder);
    pretravel(p);cout <<endl;

    return 0;
}